package Top_Interview_Questions_Review._001Tree;

import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/29 20:30
 * <p>
 * 功能描述:
 */
public class _0124 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(-10);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;

        _0124 test = new _0124();
        test.maxPathSum(root);

    }

    int max_sum = Integer.MIN_VALUE;

    /**
     *    -10
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 输出: 42
     * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-30/
     */
    public int max_gain(TreeNode node) {
        if (node == null) return 0;

        //计算左边分支最大值，左边分支如果为负数还不如不选择
        int left_gain = Math.max(max_gain(node.left), 0);
        //计算右边分支最大值，右边分支如果为负数还不如不选择，因为负数只会越加越小，所以还不如不选择
        int right_gain = Math.max(max_gain(node.right), 0);

        int price_newpath = node.val + left_gain + right_gain;

        // left->root->right 作为路径与历史最大值做比较作为路径与历史最大值做比较
        max_sum = Math.max(max_sum, price_newpath);

        // 返回经过root的单边最大分支给上游
        return node.val + Math.max(left_gain, right_gain);
    }

    public int maxPathSum(TreeNode root) {
        max_gain(root);
        return max_sum;
    }

}
